package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-17
 */

import java.util.List;

/**
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 */
public class leetcode230 {

//    List<Integer> list;
    int count;
    int ans;
    public int kthSmallest(TreeNode root, int k) {
        if (root==null) return 0;
        count = 0;

//        list = new ArrayList<>();
        inOrder(root,k);
//        int target = list.get(k - 1);

        return ans;
    }

    public void inOrder(TreeNode root, List<Integer> list){
        if (root==null) return;
        if (root.left!=null) inOrder(root.left,list);
        list.add(root.val);
        if (root.right!=null) inOrder(root.right,list);
    }

    public void inOrder(TreeNode root, int k){
        if (root==null) return;
        if (root.left!=null) inOrder(root.left,k);
        count++;
        if (count==k) ans = root.val;
        if (root.right!=null) inOrder(root.right,k);
    }


}
